//
// Created by lxinp on 2022/10/18.
//

#ifndef DATASTRUCTURE_AVL_TREE_H
#define DATASTRUCTURE_AVL_TREE_H

#include <iostream>
#include <vector>

using namespace std;


template<typename K, typename V>
class AVLTree {
private:
    struct Node {
        K key;
        V value;
        Node* left;
        Node* right;
        int height;  // calculate balance property

        Node(const K& _key, const V& _val)
            : key(_key), value(_val), left(nullptr), right(nullptr), height(0) {}
    };
    Node* root;

public:
    AVLTree();
    AVLTree(const AVLTree& other);
    ~AVLTree();
    AVLTree& operator=(const AVLTree& other);
    void clear();
    void insert(const K& key, const V& value);
    void remove(const K& key);
    V find(const K& key) const;

private:
    Node* copy(const Node* other);
    void clear(Node* subtree);
    void insert(Node* subtree, const K& key, const V& value);
    void remove(Node*& subtree, const K& key);
    V find(Node* subtree, const K& key) const;

    void rotate_left(Node*& node);
    void rotate_right(Node*& node);
    void rotate_left_right(Node*& node);
    void rotate_right_left(Node*& node);

    void rebalance(Node*& subtree);
    int height(const Node* subtree) const;
    void update_height(Node* subtree);
    void swap(Node*& first, Node*& second);

};


#endif //DATASTRUCTURE_AVL_TREE_H
